import sys
import copy

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        myBoard = [[None for _ in range(9)] for _ in range(9)]

        for r in range(9):
            for c in range(9):
                if board[r][c]!=".":
                    myBoard[r][c] = int(board[r][c])
        

        combine = [str(i) for i in range(1, 10)]
        rows = [set(combine) for _ in range(9)]
        cols = [set(combine) for _ in range(9)]
        grid = [[set(combine) for _ in range(3)] for _ in range(3)]
        diag = [set(combine) for _ in range(2)]

        def place(r, c, value):
            rows[r].remove(value)
            cols[c].remove(value)
            grid[r//3][c//3].remove(value)

        def candidates(r, c):
            return rows[r] & cols[c] & grid[r//3][c//3]

        count = 0

        for r in range(9):
            for c in range(9):
                if board[r][c]!='.':
                    place(r, c, board[r][c])
                else:
                    count+=1
        
        minNumCand = sys.maxsize
        minCands = None
        minR, minC = None, None
        while count>0:
            found = False
            for r in range(9):
                for c in range(9):
                    if board[r][c]=='.':
                        cands = candidates(r,c)
                        if len(cands)==1:
                            cand = cands.pop()
                            board[r][c]=cand
                            place(r, c, cand)
                            count-=1
                            found=True
                            
                        elif len(cands)==0:
                            return False
                        else:
                            if len(cands)<minNumCand:
                                minCands = cands
                                minR, minC = r, c
            if not found:
                break
        if count==0:return True
        for cand in minCands:
            board[minR][minC] = cand
            clone = copy.deepcopy(board)
            if self.solveSudoku(clone):
                for i in range(9):
                    board[i]=clone[i]
                    #print(board[i])
                return True
        return False

matrix = [
    ['.','.','9', '7','4','8', '.','.','.'],
    ['7','.','.', '.','.','.', '.','.','.'],
    ['.','2','.', '1','.','9', '.','.','.'],

    ['.','.','7', '.','.','.', '2','4','.'],
    ['.','6','4', '.','1','.', '5','9','.'],
    ['.','9','8', '.','.','.', '3','.','.'],
    
    ['.','.','.', '8','.','3', '.','2','.'],
    ['.','.','.', '.','.','.', '.','.','6'],
    ['.','.','.', '2','7','5', '9','.','.'],
]

Solution().solveSudoku(matrix)

for row in matrix:
    print(row)
